package dict

import (
	"math"
	"math/rand"
	"sync"
	"sync/atomic"
)

type ConcurrentDict struct {
	tables     []*shard
	count      int32
	shardCount int
}

var _ Dict = new(ConcurrentDict)

type shard struct {
	m     map[string]interface{}
	mutex sync.RWMutex
}

// 创建这么多个shardCount
// 会不会一下次创建太多了啊
func MakeConcurrentDict(shardCount int) *ConcurrentDict {
	shardCount = computeCapacity(shardCount)
	tables := make([]*shard, shardCount)
	for i := 0; i < shardCount; i++ {
		tables[i] = &shard{m: make(map[string]interface{})}
	}
	return &ConcurrentDict{
		tables:     tables,
		count:      0,
		shardCount: shardCount,
	}
}

func computeCapacity(param int) int {
	if param <= 16 {
		return 16
	}
	n := param - 1
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16
	if n < 0 {
		return math.MaxInt32
	}
	return n + 1
}

const prime32 = uint32(16777619)

// 对字符串hash
func fnv32(key string) uint32 {
	hash := uint32(2166136261)
	for i := 0; i < len(key); i++ {
		hash *= prime32
		hash ^= uint32(key[i])
	}
	return hash
}

// 获取该hash值对应的shard(shard即一个带mutex的map)
func (dict *ConcurrentDict) spread(hashCode uint32) uint32 {
	if dict == nil {
		panic("dict is nil")
	}
	n := uint32(len(dict.tables))
	return (n - 1) & hashCode
}
func (dict *ConcurrentDict) getShard(index uint32) *shard {
	if dict == nil {
		panic("dict is nil")
	}
	return dict.tables[index]
}

// return val and isExist
func (dict *ConcurrentDict) Get(key string) (val interface{}, ok bool) {
	if dict == nil {
		panic("dict is nil")
	}
	code := fnv32(key)
	index := dict.spread(code)
	shard := dict.getShard(index)
	shard.mutex.RLock()
	defer shard.mutex.RUnlock()
	val, ok = shard.m[key]
	return val, ok
}

// return result = 1 if the key is the new one else result = 0
func (dict *ConcurrentDict) Put(key string, val interface{}) (result int) {
	if dict == nil {
		panic("dict is nil")
	}
	code := fnv32(key)
	index := dict.spread(code)
	shard := dict.getShard(index)
	shard.mutex.Lock()
	defer shard.mutex.Unlock()
	if _, ok := shard.m[key]; ok {
		shard.m[key] = val
		return 0
	}
	shard.m[key] = val
	dict.addCount()
	return 1
}

// remove key
func (dict *ConcurrentDict) Remove(key string) (result int) {
	if dict == nil {
		panic("dict is nil")
	}
	code := fnv32(key)
	index := dict.spread(code)
	shard := dict.getShard(index)
	shard.mutex.Lock()
	defer shard.mutex.Unlock()
	if _, ok := shard.m[key]; ok {
		delete(shard.m, key)
		dict.subCount()
		return 1
	}
	return 0
}

// PutIfAbsent puts value if the key is not exists and returns the number of updated key-value
func (dict *ConcurrentDict) PutIfAbsent(key string, val interface{}) (result int) {
	if dict == nil {
		panic("dict is nil")
	}
	code := fnv32(key)
	index := dict.spread(code)
	shard := dict.getShard(index)
	shard.mutex.Lock()
	defer shard.mutex.Unlock()
	if _, ok := shard.m[key]; ok {
		return 0
	}
	shard.m[key] = val
	dict.addCount()
	return 1
}
// PutIfExists puts value if the key is exist and returns the number of inserted key-value
func (dict *ConcurrentDict) PutIfExists(key string, val interface{}) (result int) {
	if dict == nil {
		panic("dict is nil")
	}
	code := fnv32(key)
	index := dict.spread(code)
	shard := dict.getShard(index)
	shard.mutex.Lock()
	defer shard.mutex.Unlock()
	if _, ok := shard.m[key]; ok {
		shard.m[key] = val
		return 1
	}
	return 0
}


// ForEach traversal the dict
// it may not visits new entry inserted during traversal
func (dict *ConcurrentDict) ForEach(consumer Consumer) {
	if dict == nil {
		panic("dict is nil")
	}
	for _, shard := range dict.tables {
		shard.mutex.RLock()
		// 启动一个匿名函数
		func() {
			defer shard.mutex.RUnlock()
			for key, val := range shard.m {
				continues := consumer(key, val)
				if !continues { return }
			}
		}()
	}
}

func (dict *ConcurrentDict) Keys() []string {
	if dict == nil {
		panic("dict is nil")
	}
	keys := make([]string, dict.Len())
	i := 0
	dict.ForEach(func(key string, val interface{}) bool {
		if i < len(keys) {
			keys[i] = key
			i++
		}else {
			keys = append(keys, key)
		}
		return true
	})
	return keys
}
// RandomKey returns a key randomly
func (shard *shard) RandomKey() string {
	if shard == nil {
		panic("shard is nil")
	}
	shard.mutex.RLock()
	defer shard.mutex.RUnlock()
	// map is unordered , so  return the first one directly
	for key := range shard.m {
		return key
	}
	return ""
}
// RandomKeys randomly returns keys of the given number, may contain duplicated key
func (dict *ConcurrentDict) RandomKeys(limit int) []string {
	if dict == nil {
		panic("dict is nil")
	}
	size := dict.Len()
	// if not enough , return all
	if limit > size {
		return dict.Keys()
	}
	shardCount := dict.shardCount
	result := make([]string, limit)
	for i := 0; i < limit; {
		// randomly select shards
		shard := dict.getShard(uint32(rand.Intn(shardCount)))
		if shard == nil { continue }
		key := shard.RandomKey()
		if key != "" {
			result[i] = key
			i++
		}
	}
	return result
}

// RandomDistinctKeys randomly returns keys of the given number, won't contain duplicated key
func (dict *ConcurrentDict) RandomDistinctKeys(limit int) []string {
	if dict == nil {
		panic("dict is nil")
	}
	size := dict.Len()
	// if not enough , return all
	if limit > size {
		return dict.Keys()
	}
	shardCount := dict.shardCount
	result := make(map[string]bool)
	for i := 0; i < limit; {
		// randomly select shards
		shard := dict.getShard(uint32(rand.Intn(shardCount)))
		if shard == nil { continue }
		key := shard.RandomKey()
		if key != "" {
			if _, ok := result[key]; !ok {
				result[key] = true
				i++
			}
		}
	}
	arr := make([]string, limit)
	i := 0
	for k := range result {
		arr[i] = k
	}
	return arr
}

func (dict *ConcurrentDict) Clear() {
	*dict = *MakeConcurrentDict(dict.shardCount)
}


func (dict *ConcurrentDict) Len() int {
	if dict == nil {
		panic("dict is nil")
	}
	return int(atomic.LoadInt32(&dict.count))
}

func (dict *ConcurrentDict) addCount() {
	atomic.AddInt32(&dict.count, 1)
}
func (dict *ConcurrentDict) subCount() {
	atomic.AddInt32(&dict.count, -1)
}
